package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/24 11:19
 *
 之字打印二叉树
 层序遍历
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main2 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>>ans=new ArrayList<>();
        if(root==null)return ans;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        int level=1;
        while(!queue.isEmpty()){
            int qsize=queue.size();
            ArrayList<Integer>tmp=new ArrayList<>();
            for(int i=0;i<qsize;++i){
                TreeNode node=queue.poll();
                if(node==null)continue;

                if(level%2!=0){
                    tmp.add(node.val);
                }else{
                    tmp.add(0,node.val);
                }

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            ans.add(tmp);
            level++;
        }
        return ans;
    }
}
